import copy
import random

from query.cal_time import *


# 快速排序的时间复杂度为O(nlogn)
# 最坏的情况O(n**2)
def partition(li, left, right):
    tmp = li[left]  # 首先拿出left的元素
    while left < right:
        while left < right and li[right] >= tmp:  # 从右找比tmp小的
            right -= 1
        li[left] = li[right]  # 把右边的值写到左边
        # print(li,'right')
        while li[left] <= tmp and left < right:  # 从左找比tmp大的
            left += 1
        li[right] = li[left]  # 把左边的值写到右边空位上
        # print(li,'left')
    li[left] = tmp  # 把tmp归位
    return left  # 返回中间的下标


# 递归函数
def _quick_sort(li, left, right):
    if left < right:  # 至少两个元素
        mid = partition(li, left, right)
        _quick_sort(li, left, mid - 1)
        _quick_sort(li, mid + 1, right)


@cal_time
def quick_sort(li):
    _quick_sort(li, 0, len(li) - 1)


li = [5, 7, 4, 6, 3, 2, 1, 9, 8]
quick_sort(li)
print(li)

# 进行测试时间复杂度
li1 = list(range(10000))
random.shuffle(li1)
list1 = copy.deepcopy(li1)
print(list1)
# list2 = copy.deepcopy(li1)
quick_sort(list1)
